1. Field of the Invention
This invention relates to signal processing apparatus for analyzing and/or synthesizing signals. More particularly, the signal processing apparatus of the present invention employs pipe-line architecture for analyzing in delayed real time the frequency spectrum of an information component (having one or more dimensions) of a given temporal signal having a highest frequency of interest no greater than f.sub.0, and/or for synthesizing in delayed real time such a temporal signal from the analyzed frequency spectrum thereof. Although not limited thereto, the present invention is particularly suitable for image-processing in delayed real time the two-dimensional spatial frequencies of television images defined by a temporal video signal.
2. Description of the Prior Art
Much work has been done in modeling the operation of the human visual system. It has been found that the human visual system appears to compute a primitive spatial-frequency decomposition of luminous images, by partitioning spatial frequency information into a number of contiguous, overlapping spatial-frequency bands. Each band is roughly an octave wide and the center frequency of each band differs from its neighbors by roughly a factor of two. Research suggests that there are approximately seven bands or "channels" that span the 0.5 to 60 cycle/degree spatial-frequency range of the human visual system. The importance of these findings is that spatial frequency information more than a factor of two away from other spatial frequency information will be independently processed by the human visual system.
It has been further found that the spatial-frequency processing that occurs in the human visual system is localized in space. Thus, the signals within each spatial-frequency channel are computed over small subregions of the image. These subregions overlap each other and are roughly two cycles wide at a particular frequency.
If a sine wave grating image is employed as a test pattern, it is found that the threshold contrast-sensitivity function for the sine wave grating image rolls-off rapidly as the spatial frequency of the sine wave grating image is increased. That is, high spatial frequencies require high contrast to be seen (.perspectiveto.20% at 30 cycle/degree) but lower spatial frequencies require relatively low contrast to be seen (.perspectiveto.0.2% at 3 cycle/degree).
It has been found that the ability of the human visual system to detect a change in the contrast of a sine wave grating image that is above threshold also is better at lower spatial frequencies than at higher spatial frequencies. Specifically, an average human subject, in order to correctly discriminate a changing contrast 75% of the time, requires roughly a 12% change in contrast for a 3 cycle/degree sine wave grating, but requires a 30% change in contrast for a 30 cycle/degree grating.
Dr. Peter J. Burt, who is aware of the above-discussed properties of the human visual system, has developed an algorithm (hereinafter referred to as the "Burt Pyramid"), that he implemented by computer in non-real time, to analyze the two-dimensional spatial frequencies of an image into a plurality of separate spatial frequency bands. Each spatial frequency band (other than the lowest spatial frequency band) is preferably an octave in width. Thus, if the highest spatial frequency of interest of the image is no greater than f.sub.0, the highest frequency band will cover the octave from f.sub.0 /2 to f.sub.0 (having a center frequency at 3f.sub.0 /4); the next-to-highest frequency band will cover the octave from f.sub.0 /4 to f.sub.0 /2 (having a center frequency at 3f.sub.0 /8), etc.
Reference is made to the following list of articles, authored or co-authored by Dr. Burt, which describe in detail various aspects of the Burt Pyramid:
"Segmentation and Estimation of Image Region Properties Through Cooperative Hierarchial Computation," by Peter J. Burt, et al., IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-11, No. 12, 802-809, December 1981.
"The Laplacian Pyramid as a Compact Image Code," by Peter J. Burt, et al., IEEE Transactions on Communications, Vol. COM-31, No. 4, 532-540, April 1983.
"Fast Algorithms for Estimating Local Image Properties," by Peter J. Burt, Computer Vision, Graphics, and Image Processing 21, 368-382 (1983).
"Tree and Pyramid Structures for Coding Hexagonally Sampled Binary Images," by Peter J. Burt, Computer Graphics and Image Processing 14, 271-280 (1980).
"Pyramid-based Extraction of Local Image Features with Applications to Motion and Texture Analysis," by Peter J. Burt, SPIE, Vol. 360, 114-124.
"Fast Filter Transforms for Image Processing," by Peter J. Burt, Computer Graphics and Image Processing 16, 20-51 (1981).
"A Multiresolution Spline with Applications to Image Mosaics," by Peter J. Burt, et al., Image Processing Laboratory, Electrical, Computer, and Systems Engineering Department, Rensselaer polytechnic Institute, June 1983.
"The Pyramid as a Structure for Efficient Computation," by Peter J. Burt, Image Processing Laboratory, Electrical and Systems Engineering Department, Rensselaer Polytechnic Institute, July, 1982.
The Burt Pyramid algorithm uses particular sampling techniques for analyzing a relatively high resolution original image into a hierarchy of N (where N is a plural integer) separate component images (in which each component image is a Laplacian image comprised of a different octave of the spatial frequencies of the original image) plus a remnant Gaussian image (which is comprised of all the spatial frequencies of the original image below the lowest octave component Laplacian image). The term "pyramid" as used herein, relates to the successive reduction in the spatial frequency bandwidth and sample density of each of the hierarchy of component images in going from the highest octave component image to the lowest octave component image.
A first advantage of the Burt Pyramid algorithm is that it permits the original high-resolution image to be synthesized from the component images and the remnant image without the introduction of spurious spatial frequencies due to aliasing. A second advantage of the Burt Pyramid algorithm is that the spatial frequency bandwidth of one octave of each of the hierarchy of the component images matches the properties of the human visual system, discussed above. This makes it possible to selectively process or alter the spatial frequencies of individual ones of the hierarchy of component images in different independent ways (i.e., without the signal processing of any one component image significantly affecting any other component image), in order to enhance or produce some other desired effect in the synthesized image derived from the processed component images. An example of such a desired effect is the multiresolution spline technique described in detail in the article "A Multiresolution Spline with Applications to Image Mosiacs," listed above.
Until now, the Burt Pyramid algorithm has been implemented in non-real time by means of a general purpose digital computer. The level of each picture element (pixel) sample of an original image is represented by a multibit (e.g., 8 bit) number stored at an individual address location of a computer memory. For example, a relatively high-resolution two-dimensional original image comprised of 2.sup.9 (512) pixel samples in each of its two dimensions requires a large memory of 2.sup.18 (262,144) address locations for respectively storing each of the multibit numbers representing the levels of the respective pixel samples comprising the original image.
The original image stored in the memory can be processed by a digital computer in accordance with the Burt Pyramid algorithm. This processing involves the iterative performance of such steps as convolution of pixels samples with a predetermined kernel weighting function, sample decimation, sample expansion by interpolation, and sample subtraction. The size of the kernel function (in either one or more dimensions) is relatively small (in terms of the number of pixels) compared to the size in each dimension of the whole image. The subregion or window of image pixels (equal in size to the kernel function and symmetrically disposed, in turn, about each image pixel) is multiplied by the kernel weighting function and summed in a convolution computation.
The kernel weighting function is chosen to operate as a low-pass filter of the multi-dimensional spatial frequencies of the image being convoluted. The nominal "cut-off" (also known in the filter art as "corner" or "break") frequency of the low-pass filter characteristics provided in each dimension by the kernel function is chosen to be substantially one-half the highest frequency of interest in that dimension of the signal being convolved. However, this low-pass filter characteristic need not have a "brick wall" roll-off at a given cut-off frequency, but can have a relatively gradual roll-off, in which case a nominal cut-off frequency is defined as the frequency at which some preselected value (e.g., 3 db) of attenuation in the gradual roll-off takes place. Filters with more gentle roll-off characteristics can be used because the Burt Pyramid inherently compensates for the introduction of spurious frequencies, due to aliasing, caused by a gradual roll-off low-pass filter characteristic. The convolved image is decimated by effectively throwing away, in each of the respective dimensions of the image successively considered, every other convolved pixel, thereby reducing the number of pixels in the convolved image in each dimension thereof by one-half. Since an image is conventionally a two-dimensional image, a convolved-decimated image is comprised of only one-fourth the number of pixels contained in the image prior to such decimation. The reduced number of pixel samples of this convolved-decimated image (which is called a Gaussian image) are stored in a second memory.
Starting with the stored original image pixel samples, the aforesaid convolution-decimation procedure is iteratively performed N times (where N is a plural integer) thereby resulting in (N+1) images comprised of the original high-resolution image and a heirarchal pyramid of N reduced-resolution Gaussian additional images, wherein the number of pixel samples (sample density) in each dimension of each additional image is only one-half the number of pixel samples in each dimension of the immediately preceding image. If the original, high-resolution stored image is designated G.sub.0, the hierarchy of N stored additional images can be respectively designated G.sub.1 through G.sub.N, with the successively reduced number of pixel samples of each of these N additional images being stored in a separate one of N memories. Thus, counting the stored original image, there are a total of N+1 memories.
In accordance with the non-real time implementation of the Burt Pyramid algorithm, the next computational procedure is to generate interpolated-value additional samples between each pair of stored G.sub.1 pixel samples in each dimension thereof, thereby expanding the reduced sample density of the stored G.sub.1 image back to the sample density of the original stored G.sub.0 image. The digital value of each of the pixel samples of the expanded G.sub.1 image is then subtracted from the stored digital value of the corresponding pixel sample of the original G.sub.0 image to provide a difference image (known as a Laplacian image). This Laplacian image (designated L.sub.0), which has the same sample density as the original G.sub.0 image, is comprised of those spatial frequencies contained in the original image within the octave f.sub.0 /2 to f.sub.0 --plus, often, a small lower spatial frequency error-compensating component that corresponds to the loss of information caused respectively by the decimation step employed in deriving the reduced sample density of the G.sub.1 image and in the introduction of interpolated value samples that occurs in expanding the sample density back to that of the original G.sub.0 image. This Laplacian image L.sub.0 then replaces the original image G.sub.0 in storage in the first of the N+1 pyramid memories.
In a similar manner, by iterating this procedure, a heirarchy comprised of N-1 additional LaPlacian images L.sub.1 through L.sub.N-1 is derived, in turn, and written into a corresponding one of the respective additional N-1 memories in which the Gaussian images G.sub.1 through G.sub.N-1 are stored (thereby replacing in memory the Gaussian images G.sub.1 through G.sub.N-1). The Gaussian image G.sub.N (having the most reduced sample density) is not replaced in its corresponding memory by a Laplacian image, but remains stored in the memory as a Gaussian remnant comprised of the lowest spatial frequencies (i.e., those below the L.sub.N-1 octave) contained in the original image.
The Burt Pyramid algorithm permits the original image to be restored, without aliasing, by an iterative computational procedure which involves successive steps of expanding the stored remnant image G.sub.N to the sampling density of the L.sub.N-1 image and then adding it to the stored Laplacian image L.sub.N-1 to derive a sum image. This sum image is expanded in a similar manner and added to the Laplacian image L.sub.N-2, etc., until the original high-resolution image has been synthesized by the summation of all the Laplacian images and the remnant image. Furthermore, following the analysis of one or more original images into N Laplacian images and a Gaussian remnant, it is possible to introduce any particular desired image processing or altering step (such as splining) before synthesizing a complete high-resolution image therefrom.